import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 涛
 * Date: 2023-10-15
 * Time: 14:46
 */
public class Sort {
    public static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        int i = left;
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, i, left);
        return left;
    }

    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 非递归快速排序
     * @param array
     */
    public static void quickSortNor(int[] array) {
        int start = 0;
        int end = array.length - 1;
        Stack<Integer> stack = new Stack<>();
        int pivot = partition(array, start, end);

        if (pivot - 1 > start) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if (pivot + 1 < end) {
            stack.push(pivot + 1);
            stack.push(end);
        }

        while (!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition(array, start, end);

            if (pivot - 1 > start) {
                stack.push(start);
                stack.push(pivot - 1);
            }
            if (pivot + 1 > end) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }
    /**
     * 归并排序
     *
     * 稳定
     */
    public static void mergeSort(int[] array) {
        int start = 0;
        int end = array.length - 1;
        mergeSortFun(array, start, end);
    }
    public static void mergeSortFun(int[] array, int start, int end) {
        if(start >= end) {
            return;
        }
        //中间位置
        int mid = (start + end) / 2;
        //左边分割
        mergeSortFun(array, start, mid);
        //右边分割
        mergeSortFun(array, mid + 1, end);
        //合并
        merge(array, start, mid, end);
    }
    public static void mergeSortNor(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            for(int i = 0; i < array.length; i = i + gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                if(mid >= array.length) {
                    mid = array.length - 1;
                }
                if(right >= array.length) {
                    right = array.length - 1;
                }
                merge(array, left, mid, right);
            }
            gap *= 2;
        }

    }
    public static void merge(int[] array, int left, int mid, int right) {
        //左右两块数组的起始位置s1,e1,s2,e2
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        //新的数组,下标
        int[] tmpArray = new int[right - left + 1];
        int k = 0;
        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmpArray[k++] = array[s1++];
            } else {
                tmpArray[k++] = array[s2++];
            }
        }
        while (s1 <= e1) {
            tmpArray[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmpArray[k++] = array[s2++];
        }
        //拷贝到原数组
        for (int i = 0; i < tmpArray.length; i++) {
            array[i + left] = tmpArray[i];
        }
    }
    /**
     * 计数排序
     * 时间复杂度 : O(MAX(N+范围))
     * 空间：O(范围)
     * 稳定，下面写的不稳定
     */
    public static void countSort(int[] array) {
        //申请计个数的数组
        int minVal = 0;//最大值下标
        int maxVal = 0;//最小值下标
        for (int i = 0; i < array.length; i++) {
            if(array[minVal] > array[i]) {
                minVal = i;
            }
            if (array[maxVal] < array[i]) {
                maxVal = i;
            }
        }
        int len = maxVal - minVal + 1;
        int[] count = new int[len];

        //遍历array数组，把数据出现的次数存储到计数数组中
        for (int i = 0; i < array.length; i++) {
            count[array[i] - minVal]++;
        }
        //计数数字已经存放了每个数据出现的次数
        //遍历计数数组，把实际的数据写回到array数组中
        int index = 0;
        for(int i = 0; i < count.length; i++) {
            while(count[i] > 0) {
                //重新写会array，array从0位置开始写
                array[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }
}
